package com.lw.leetcode.sort.c;

import com.lw.test.util.Utils;

import java.util.TreeMap;

/**
 * Created with IntelliJ IDEA.
 * 2398. 预算内的最多机器人数目
 *
 * @author liw
 * @version 1.0
 * @date 2022/11/17 16:13
 */
public class MaximumRobots {

    public static void main(String[] args) {
        MaximumRobots test = new MaximumRobots();

        // 3
//        int[] chargeTimes = {3, 6, 1, 3, 4};
//        int[] runningCosts = {2, 1, 3, 4, 5};
//        int budget = 25;

        // 3
        int length = 10000;
        int[] chargeTimes = Utils.getArr(length, 1, 100000);
        int[] runningCosts = Utils.getArr(length, 1, 100000);
        int budget = 25000;
        System.out.println(budget);

        int i = test.maximumRobots(chargeTimes, runningCosts, budget);
        System.out.println(i);
    }

    public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
        long sum = 0;
        int length = chargeTimes.length;
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int index = 0;
        int max = 0;
        for (int i = 0; i < length; i++) {
            int a = chargeTimes[i];
            int b = runningCosts[i];
            sum += b;
            map.merge(a, 1, (p1, p2) -> p1 + p2);
            int key = 0;
            if (!map.isEmpty()) {
                key = map.lastKey();
            }
            long l = sum * (i - index + 1) + key;
            while (l > budget) {
                sum -= runningCosts[index];
                int chargeTime = chargeTimes[index++];
                int c = map.get(chargeTime);
                if (c == 1) {
                    map.remove(chargeTime);
                } else {
                    map.put(chargeTime, c - 1);
                }
                key = 0;
                if (!map.isEmpty()) {
                    key = map.lastKey();
                }
                l = sum * (i - index + 1) + key;
            }
            max = Math.max(max, i - index + 1);
        }
        return max;
    }

}
